The present invention relates generally to xe2x80x9cfilling inxe2x80x9d the RGB data obtained from digital camera sensors, and to generating interpolated image data values when a digitally encoded image is magnified to a larger size, and particularly to a system and method for performing image data interpolations using spatially limited two-dimension xe2x80x9cFIR-likexe2x80x9d filters and yet generating images that appear continuous, undistorted and sharp.
The present invention addresses two related problems: filling in RGB data obtained from digital camera sensors, and to generating interpolated image data values when a digitally encoded image is magnified to a larger size.
Referring to FIG. 1, the first problem concerns the fact that digital camera sensors generate only one color value (for red, green or blue) at each pixel position of the image, creating a pattern of red, green and blue pixels called a mosaic. The specific pattern shown in FIG. 2 is referred to as the Bayer mosaic pattern. However, all three R, G, B color values are needed for every pixel position to produce a full-color image. In this situation, when image data is first received from the camera sensor, only half the pixels in the image contain an intensity value for the color green, only one fourth of the pixels in the image contain an intensity value for the color blue, and only one fourth of the pixels in the image contain an intensity value for the color red. The goal is to produce the most xe2x80x9caccuratexe2x80x9d possible intensity values of the missing green, blue and red intensity values, essentially predicting what those intensity values would have been if the camera sensor had been able to record them.
Referring to FIG. 2, the second problem concerns the magnification of an image, such as by a factor of four (i.e., the width and height of the image are each doubled). In this situation, it is assumed that the system already has RGB or YUV values, or some other equivalent set of values, representing the initial set of image pixels. However, three fourths of the pixels in the magnified image initially have no image data values, and thus those values have to be generated from the information available in the original pixels (I), which have now been mapped to all the even index positions in the magnified image (J). For magnification factors other than four, the number of pixels that initially have no value will depend on the value of the magnification factor.
While there are literally hundreds of articles and patents addressing interpolation techniques for handling the missing RGB data problem and image data magnification, there are three primary image data interpolation techniques that are used in prior art systems: (1) pixel replication, (2) linear/bilinear interpolation, and (3) cubic/bicubic interpolation. Pixel replication is the simplest image data interpolation technique. In pixel replication, each interpolated pixel value is generated simply by replicating the value of a neighboring pixel in the initial set of pixels. The main advantage of pixel replication is that the interpolation is computationally very simple. The primary disadvantage of this technique is that the quality of the resulting image is poor.
In linear/bilinear interpolation, each interpolated pixel value is generated by essentially xe2x80x9caveragingxe2x80x9d the values of the two or four closest neighboring pixels in the initial set of pixels. Linear interpolation is used when performing data interpolation on a one-dimensional data set. Linear interpolation generates the interpolated pixel value based on the xe2x80x9caveragexe2x80x9d of the values of the two closest neighboring pixels, one on the left and one on the right, and is a function having terms proportional to 1 and x, where x is the coordinate of the interpolated pixel value. Bilinear interpolation is used when performing image data interpolation on a two-dimensional image. Bilinear interpolation generates the interpolated pixel value based on the xe2x80x9caveragexe2x80x9d of the four closest neighboring pixels, one in each of the northwest, northeast, southeast and southwest directions, and is a function having terms proportional to 1, x, y and xy, where x and y are the coordinates of the interpolated pixel value. Although the quality of the resulting image is better than that produced by pixel replication, the image quality is still relatively poor.
In cubic/bicubic interpolation, each interpolated pixel value is generated based on the values of all pixels in the initial set of pixels. Each interpolated pixel is set to a value such that the piecewise cubic polynomial (sometimes called a cubic spline) formed by the pixels in the resulting image has continuous first and second derivatives (i.e., has second order smoothness). Cubic interpolation is used when performing data interpolation on a one-dimensional data set. The interpolated pixel value generated using cubic interpolation is a function having 1, x, x2 and x3 terms, where x is the coordinate of the interpolated pixel value. Bicubic interpolation is used when performing image data interpolation on a two-dimensional image. The interpolated pixel value generated using bicubic interpolation is a function having 1, x, y, xy, x2, x2y, x2y2, x2y3, x3, x3y, x3y2 and x3y3 terms, where x and y are the coordinates of the interpolated pixel value. The quality of the image produced by cubic/bicubic interpolation is usually very good. Unfortunately, however, the computation and memory requirements of cubic/bicubic interpolation is very high because all pixel values in the image are required to generate each interpolated pixel value.
Goal 1: Low Distortion. Alternately stated, it is a goal to avoid the use of higher order cross terms, herein called xe2x80x9cdistortionxe2x80x9d terms because they are responsible for introducing artifacts and distortions in interpolated image data. For bilinear interpolation, the distortion term is xy, having a xe2x80x9ctotal powerxe2x80x9d of two. For biquadratic interpolation, the distortion terms are terms having a xe2x80x9ctotal powerxe2x80x9d greater than two (namely x2y, xy2 and x2y2). For bicubic interpolation, the distortion terms are those having total power greater than three (namely x3y, x3y2, x2y2, x3y3, x2y3 and xy3) Distortion terms are undesirable because they increase the memory required to generate the interpolated image data and generate image artifacts along the diagonals of each rectangular region formed by any four adjacent pixels.
Goal 2: Smoothness. The interpolated image data should represent a smooth and continuous image surface, without discontinuities. If a group of original, neighboring image data points lie on a polynomial surface (e.g., plane or quadratic surface), the new interpolated image data points used to fill in holes between the original image data points should lie on the same polynomial surface.
Goal 3: Continuous turning tangent planes. The tangent planes of the image surface represented by the interpolated image data should be xe2x80x9ccontinuously turning,xe2x80x9d without discontinuities. In other words, the two-dimensional spatial first derivative of the surface should be continuous, providing a surface without any sharp angles.
Goal 4: The tangent plane of the image surface represented by the interpolated image data at each location for which an interpolated value is generated should be substantially parallel (i.e., visually indistinguishable from a plane that is parallel) to a secant plane formed by adjacent ones of the data points corresponding to the initial data values.
Goals 1, 2 and 3 ensure that the image after interpolation is xe2x80x9cpleasingxe2x80x9d by minimizing the visibility of artifacts in the interpolated image such as lines. Goal 4 ensures that sharp lines in the image remain sharp or near sharp in the interpolated image.
In summary, the present invention is a system and method for generating interpolated pixel data values that begins with an initial image data set that is a subset of data values in a data array fk,l representing data values at corresponding positions (k,l). Some of the fk,l values are initially undefined, while others at positions where both k and l are even numbers have initially defined values.
For filling in midpoints (half way between pixels having assigned values), an interpolated value is generated for each initially undefined fk,l value in accordance with the pixel filling filter equation:                               f                      k            ,            l                          =                              ∑                          i              ,              j                                      xe2x80x83                                ⁢                      xe2x80x83                    ⁢                                    P                                                k                  -                                      2                    ⁢                    i                                                  ,                                  l                  -                                      2                    ⁢                    j                                                                        ⁢                          d                              i                ,                j                                                                        (        1        )            
wherein
di,j are the subset of fk,l values which have defined values prior to the generation of the interpolated fk,l values;
Pk,l are coefficients, no more than sixteen of which have non-zero values; and each non-zero Pk,l coefficient is an integer divided by an integer power of two.
For filling in quarter points, a filter equation analogous to equation 1, but with 2i and 2j replaced by 4i and 4j is used. Alternately, filtering using equation is performed twice, but the resulting image will usually be less sharp.
The pixel values generated in accordance with the pixel filling filter equation have the following properties:
(A) the set of fk,l values (including the mapped di,j values) represent a smooth surface that is continuous; whenever a local set of the initial data points di,j (i.e., neighboring ones of the fk,l points where both k and l are even) all fall on a polynomial surface (e.g., plane or paraboloid), the interpolated fk,l values that are located between the initial data points also fall on that same polynomial surface;
(B) the surface represented by the set of fk,l values has a two-dimensional spatial first derivative that is continuous; and
(C) the surface represented by the set of fk,l values has at each location (k,l) for which an interpolated value is generated a tangent plane that is parallel or substantially parallel to a secant plane formed by adjacent ones of the data points (k,l) corresponding to the initial data values di,j.
To magnify an image by a specified factor other than an integer power of four, the image is magnified in two stages. In the first stage the image is magnified by a factor that is smaller than the specified factor, but which is an integer power of four. (The first stage is skipped if the specified magnification factor is less than four.) The newly created pixels are generated using the pixel filling filter of the present invention. In the second stage the pixel values resulting from the first stage are remapped to new locations based on the specified magnification factor. This mapping will usually map some pixel values to non-pixel positions, and will always leave many pixel positions with no assigned pixel value. A new type of filter, herein called a xe2x80x9cBarycentric interpolation filter,xe2x80x9d is used to compute pixel values at each of the pixel positions P not assigned a pixel value by the remapping. For each such pixel position P, a reference triangle is selected by selecting the three closest pixel values, at positions A, B and C, having pixel values a, b and c, respectively. The coordinates of those pixel values and the pixel position P for which a pixel value p is to be generated are mapped into the Barycentric coordinate system. The coordinates (u, v, w) of the pixel position P in the Barycentric coordinate system are then used as weights for generating a pixel value p=ua+vb+wc that lies on the plane that passes through the vertices A, B and C of the reference triangle.